package com.smh;

import org.junit.jupiter.api.Test;

import java.util.ArrayDeque;
import java.util.List;

/**
 * @author shiminghui
 * @date 2025/3/14 16:44
 * @description: TODO
 */
public class _043_图_拓扑排序 {

    @Test
    public void test01() {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        Vertex v6 = new Vertex("v6");
        Vertex v7 = new Vertex("v7");
        Vertex v8 = new Vertex("v8");


        v1.setEdges(List.of(new Edge(v1, v3, 1)));
        v2.setEdges(List.of(new Edge(v2, v3, 1)));
        v3.setEdges(List.of(new Edge(v3, v5, 1)));
        v4.setEdges(List.of(new Edge(v4, v5, 1)));
        v5.setEdges(List.of(new Edge(v5, v6, 1)));
        v6.setEdges(List.of(new Edge(v6, v7, 1)));
        v7.setEdges(List.of(new Edge(v7, v8, 1)));
//        v8.setEdges(List.of(new Edge(v8, v7, 1)));

        topoSort2(List.of(v1, v2, v3, v4, v5, v6, v7, v8));
    }

    /**
     * 拓扑排序, 递归实现
     *
     * @param vertexList
     */
    private void topoSort2(List<Vertex> vertexList) {
        ArrayDeque<String> stack = new ArrayDeque<>();
        for (Vertex vertex : vertexList) {
            doTope(vertex, stack);
        }
        while (!stack.isEmpty()) {
            System.out.println(stack.removeLast());
        }
    }

    private void doTope(Vertex v, ArrayDeque<String> stack) {
        if (v.getStatus() == 2) {
            return;
        }
        if (v.getStatus() == 1) {
            throw new RuntimeException("出现环了");
        }
        v.setStatus(1);
        List<Edge> edges = v.getEdges();
        if (edges == null) {
            v.setStatus(2);
            return;
        }
        for (Edge edge : edges) {
            doTope(edge.getTo(), stack);
        }
        stack.addLast(v.getName());
        v.setStatus(2);
    }


    /**
     * 拓扑排序,如果出现环了怎么办,怎么检测
     * 只需要添加一个集合用来记录访问过的顶点,如果最后集合元素与顶点数一致，则说明没有环
     */
    private void topoSort(List<Vertex> vertexList) {
        // 遍历所有顶点，统计入度
        for (Vertex vertex : vertexList) {
            List<Edge> edges = vertex.getEdges();
            if (edges == null) {
                continue;
            }
            for (Edge edge : edges) {
                edge.getTo().setInDegree(edge.getTo().getInDegree() + 1);
            }
        }
        // 遍历所有顶点，找到入度为0的顶点，入队
        ArrayDeque<Vertex> deque = new ArrayDeque<>();
        for (Vertex vertex : vertexList) {
            if (vertex.getInDegree() == 0) {
                deque.addLast(vertex);
            }
        }
        // 出队，并删除入度为0的顶点，更新入度，重复此过程
        while (!deque.isEmpty()) {
            Vertex vertex = deque.removeFirst();
            System.out.println(vertex);
            if (vertex.getEdges() == null) {
                continue;
            }
            // 更新入度,并将入度为0的顶点入队
            for (Edge edge : vertex.getEdges()) {
                edge.getTo().setInDegree(edge.getTo().getInDegree() - 1);
                if (edge.getTo().getInDegree() == 0) {
                    deque.addLast(edge.getTo());
                }
            }
        }
    }

    private static class Edge {
        private Vertex from;
        private Vertex to;
        private int weight;

        public Edge(Vertex from, Vertex to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        public Edge(Vertex from, Vertex to) {
            this.from = from;
            this.to = to;
        }

        public Vertex getFrom() {
            return from;
        }

        public void setFrom(Vertex from) {
            this.from = from;
        }

        public Vertex getTo() {
            return to;
        }

        public void setTo(Vertex to) {
            this.to = to;
        }

        public int getWeight() {
            return weight;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }
    }

    private static class Vertex {
        private String name;
        private List<Edge> edges;
        private boolean isVisited = false;
        private int inDegree = 0; // 入度
        private int status = 0; // 0 未访问 1 访问中 2 访问结束

        public Vertex(String name) {
            this.name = name;
        }

        public Vertex(String name, List<Edge> edges) {
            this.name = name;
            this.edges = edges;
        }

        public int getStatus() {
            return status;
        }

        public void setStatus(int status) {
            this.status = status;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public List<Edge> getEdges() {
            return edges;
        }

        public void setEdges(List<Edge> edges) {
            this.edges = edges;
        }

        public boolean isVisited() {
            return isVisited;
        }

        public void setVisited(boolean visited) {
            isVisited = visited;
        }

        public int getInDegree() {
            return inDegree;
        }

        public void setInDegree(int inDegree) {
            this.inDegree = inDegree;
        }

        @Override
        public String toString() {
            return "Vertex{" +
                    "name='" + name + '\'' +
                    '}';
        }
    }

}
